\documentclass{beamer}
\usepackage[utf8]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Call-site optimization for \commonlisp{}}

\author{Robert Strandh}
\institute{
LaBRI, University of Bordeaux
}
\date{April, 2021}

%\inputtex{macros.tex}


\begin{document}
\frame{
\titlepage
\vfill
\small{European Lisp Symposium, Online Everywhere \hfill ELS2021}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Context: The \sicl{} project}
https://github.com/robert-strandh/SICL
\vskip 0.25cm
Several objectives:
\vskip 0.25cm
\begin{itemize}
\item Create high-quality \emph{modules} for implementors of
  \commonlisp{} systems.
\item Improve existing techniques with respect to algorithms and data
  structures where possible.
\item Improve readability and maintainability of code.
\item Improve documentation.
\item Ultimately, create a new implementation based on these modules.
\end{itemize}
}

\frame{
  \frametitle{Context for this work}
  Cost of function calls in \commonlisp{}:
  \vskip 0.25cm
  \begin{itemize}
  \item Late binding.
  \item Optional parameters and keyword parameters.
  \item Callee must often check types of arguments.
  \item Arguments must be boxed.
  \item Generic functions can be dynamically updated.
  \item Multiple return values complicate caller.
  \end{itemize}
}

\frame{
  \frametitle{Late binding}
  \begin{itemize}
  \item Usually handled by an indirection through a symbol.
  \item In SICL, handled by an indirection through a \emph{function cell} in
    a first-class global environment.
  \item Late binding is no longer respected in the presence of compiler
    macros or inlining.
  \end{itemize}
}

\frame{
  \frametitle{Optional parameters and keyword parameters}
  \begin{itemize}
  \item Callee must at least check the argument count.
  \item With optional parameters, a conditional branch is required.
  \item Keyword parameters require iterating over remaining arguments.
  \end{itemize}
  \vskip 0.25cm
  Mitigated by the use of compiler macros.  But then late binding is
  no longer respected.
}

\frame{
  \frametitle{Callee must check types of arguments}
  Necessary if specific types are required to fulfill contract.
  \vskip 0.25cm
  Mitigated by inlining.  But then late binding is no longer
  respected.
}

\frame{
  \frametitle{Arguments must be boxed}
  \vskip 0.25cm
  Mitigated by multiple entry points for each function.
  \vskip 0.25cm
  Used by Allegro \commonlisp{}.
  \vskip 0.25cm
  A similar technique is used for (a single) unbox return value.
}

\frame{
  \frametitle{Generic functions can be dynamically updated}
  \vskip 0.25cm
  Callers can make no assumption about applicable methods.
}

\frame{
  \frametitle{Multiple return values complicate caller}
  \vskip 0.25cm
  Mitigated by recognizing that most callers require at most a single
  return value.
  \vskip 0.25cm
  Callee can then always set value in one register.
}

\frame{
  \frametitle{Current work}
  \vskip 0.25cm
  We propose a general technique for call-site optimization that can
  handle many of these issues.
}

\frame{
\frametitle{Previous work}
To our knowledge, no work on call-site optimization has been published
in the context of \commonlisp{}.
\vskip 0.25cm
\begin{itemize}
\item Inline caching.
\item Ctors.
\item Sealing.
\end{itemize}
\vskip 0.25cm
See paper for inline caching and sealing.  We will discuss only Ctors.
}

\frame{
\frametitle{Previous work (ctors)}
\begin{itemize}
\item Introduced by Gerd Moellmann into CMUCL in 2002.
\item Has since been included also in SBCL and Clasp.
\item A similar mechanism is used in Allegro \commonlisp{}.
\end{itemize}
}

\frame{
\frametitle{Previous work (ctors)}
\begin{itemize}
\item Can be used for certain functions that are often called with
  some arguments being literals.
\item In particular, it is used for \texttt{make-instance}.
\item In Clasp, also used for \texttt{change-class} and
  \texttt{reinitialize-instance}.
\end{itemize}
}

\frame{
\frametitle{Previous work (ctors)}
How it works:
\begin{itemize}
\item A compiler macro is used to replace the original call by a call
  to a \emph{funcallable object} that is specific to the literal
  arguments given.
\item The \emph{funcallable instance function} of the funcallable
  object is altered when the callee is altered.
\item For \texttt{make-instance}, alterations can consist of changes
  to class definitions.
\end{itemize}
}

\frame{
\frametitle{Previous work (ctors)}
\begin{itemize}
\item Optimization is accomplished by the manual creation of a
  compiler macro.
\item There is an additional indirection through the funcallable
  object.
\end{itemize}
\vskip 0.25cm
Our technique can be seen as an automatic and low-overhead version of
Ctors.
}

\frame{
\frametitle{Definition: function call}
Code that accomplishes the following tasks:
\vskip 0.25cm
\begin{itemize}
\item Access the arguments and put them in the place where the call
  protocol expects them.
\item Access the function object associated with the name.
\item From the function object, access its static environment.
\item From the function object, access the entry point.
\item Transfer control to the entry point (saving the return
  address).
\item Upon callee return, access the return values in the place where
  the callee put them, and store them in the place where they are
  needed for further computation.
\end{itemize}
}

\frame{
\frametitle{Function call, typical implementation}
\begin{itemize}
\item The compiler generates the code once, when the caller is
  compiled.
\item Since the callee can change, a \emph{function-call protocol} is
  used by all callers and callees.
\end{itemize}
}

\frame{
\frametitle{Our technique}
Optimize calls where the name of the callee is known statically:
\vskip 0.25cm
\begin{itemize}
\item A function form where the operator is a symbol naming a function
  in the global environment.
\item A function form where the operator is the symbol
  \texttt{funcall} and the first argument is either a literal symbol
  or a \texttt{function} special form with a function name.
\item A function form where the operator is the symbol
  \texttt{apply} and the first argument is either a literal symbol
  or a \texttt{function} special form with a function name.
\end{itemize}
\vskip 0.25cm
Others are possible, and we might consider others in the future.
\vskip 0.25cm
In this talk, only the first case is considered.  Others are similar.
%% \begin{figure}
%% \begin{center}
%% \inputfig{fig-method-combinations.pdf_t}
%% \end{center}
%% \end{figure}
}


\frame{
\frametitle{Our technique, ordinary function form}
\begin{itemize}
\item Code emitted by a caller consists of an unconditional
  \emph{jump} instruction.
\item The address field of the jump instruction is filled in by the
  callee.
\item The code for the function call (according to our definition) is
  contained in an object called a \emph{trampoline snippet} (or
  \emph{snippet} for short).
\item The snippet ends with a second unconditional \emph{jump}
  instruction back to the instruction following the first such
  instruction.
\end{itemize}
}

\frame{
\frametitle{Trampoline snippet}
\begin{figure}
\begin{center}
\inputfig{fig-snippet.pdf_t}
\end{center}
\end{figure}
}

\frame{
  \frametitle{Default snippet}
  Created in some situations:
  \vskip 0.25cm
  \begin{itemize}
  \item When a new caller refers to an undefined callee.
  \item When a callee is redefined or made to be undefined.
  \end{itemize}
  \vskip 0.25cm
  The default snippet contains the instructions for the function-call
  protocol.
}

\frame{
\frametitle{Default snippet}
\begin{figure}
\begin{center}
\inputfig{fig-default-snippet.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Information provided when caller is defined}
For each call site in the caller:
\vskip 0.25cm
\begin{itemize}
\item Name of callee.
\item Number of arguments.
\item Type of each argument.
\item For each argument, whether it is boxed or unboxed.
\item For each argument, its location (register or stack position).
\item Information about return values (more in the paper).
\end{itemize}
}

\frame{
\frametitle{Benefits}
\vskip 0.25cm
\begin{itemize}
\item Fewer indirections.
\item Static environment does not need to be loaded when it is empty.
\item Argument parsing is greatly simplified, especially for keyword
  parameters.
\item Unboxed arguments can be handled.
\item Sometimes, the entire callee can be ``inlined'' into the snippet.
\end{itemize}
}

\frame{
\frametitle{Disadvantages}
\vskip 0.25cm
\begin{itemize}
\item Fairly complicated technique.
\item Two unconditional jumps.  But these are nearly free with modern
  processors.
\item Complicates the garbage collector some.
\end{itemize}
}

\frame{
\frametitle{Future work}
Our technique has not yet been implemented.
\vskip 0.25cm
\begin{itemize}
\item Create a native executable for SICL using only default
  snippets. 
\item Implement remaining details of out technique.
\end{itemize}
}

\frame{
  \frametitle{Acknowledgments}
  \begin{itemize}
  \item Frode Fjeld.
  \item David Murray.
  \item Duane Rettig.
  \end{itemize}
}

\frame{
\frametitle{Thank you}
}

%% \frame{\tableofcontents}
%% \bibliography{references}
%% \bibliographystyle{alpha}

\end{document}
